Tutorial 1 - Using a Quantum Device to solve MIS

Maximum Independent Set (MIS) is a standard and widespread graph problem in scheduling, network theory, error correction, and even in the quantum sector as part of more general optimization algorithms (e.g., QUBO formulations) or as a benchmark on quantum annealers or neutral atom devices.

There is currently no known polynomial-time algorithm for general graphs running on classical (non-quantum) devices, which means that, in practice, finding an exact solution for large graphs is generally not possible due to time and hardware limitations. For this reason, most applications of MIS must satisfy themselves with finding approximate solutions. As it turns out, in some cases, even finding approximate solutions is considered hard. For these reasons, there is high interest in solving MIS on Quantum Devices.

This library does just that: it compiles an MIS into a form suited for execution on existing analog quantum hardware, such as the commercial QPUs produced by Pasqal. No knowledge of quantum programming is necessary and no quantum computer is needed to test-drive the library. In this tutorial, we will walk you through executing an instance of MIS, using both classical and quantum methods.

By the end of this notebook, you will know how to:

• Setup import for standard MIS benchmarking DIMACS datasets.
• Setup compilation and execution of these graphs for execution on both Classical and Quantum Device (either an emulator or a physical QPU).
• Launch the execution and extract relevant results.

The MIS problem

The MIS problem can be formulated as follows: given a graph $G=(V,E)$, an independent set is a subset of vertices $S\subseteq V$ such that no two vertices in $S$ are connected by an edge. The MIS problem then seeks to find the largest independent set in $G$.

Dataset preparation

As in any MIS process, we first need to load and prepare data in a suitable graph format. For this tutorial, we will use the standard benchmark DIMACS datasets (external) of various sizes and convert them to supported Networkx (external) graph types.

In [1]:

# Ignore warnings for this tutorial.
import logging
import os
import sys

logger = logging.getLogger()
logger.disabled = True

sys.stderr = open(os.devnull, 'w')

In [2]:

import networkx as nx

# Create a new networkx graph instance to be populated with DIMACS data.
graph = nx.Graph()


with open("./datasets/dimacs/a265032_1tc.32.txt", "r") as f:
    for line in f:
        if line.startswith("c"):  # Comment line in DIMACS file.
            continue
        elif line.startswith("p"):  # Problem definition, i.e. # nodes and edges.
            _, _, num_nodes, num_edges = line.strip().split()
            # Preset graph node labels as there might be isolated ones.
            graph.add_nodes_from(range(1, int(num_nodes) + 1))

        elif line.startswith("e"):
            _, node1, node2 = line.strip().split()
            graph.add_edge(int(node1), int(node2))

# Let's check what the graph looks like.
print(graph)

Graph with 32 nodes and 68 edges

Solving MIS using a non-quantum solver

Let's first solve this instance of MIS using standard heuristics.

In [3]:

from mis import MISSolver, MISInstance, SolverConfig
# Define classical solver configuration

# Use a default configuration for the library.
# By default, the library uses a classical (non-quantum)
# heuristic solver.
config = SolverConfig()

# Create the MIS instance.
instance = MISInstance(graph)

# Run the solver and retrieve results.
solver = MISSolver(instance, config)
solutions = solver.solve()

# Display results
solutions[0].draw()
print("Solution nodes: ", solutions[0].nodes)
print("Solution frequency:", solutions[0].frequency)
print("Solution size:", solutions[0].size)

preprocessing - current kernel size is 32

Solution nodes:  [1, 2, 4, 8, 9, 15, 16, 18, 25, 26, 30, 32]
Solution frequency: 1.0
Solution size: 12

In this instance, we have used the default (non-quantum) solver. This solver is based on the approximate MIS solver in Networkx (external). From its inherent heuristic and non-deterministic nature, this solver does not guarantee optimality in solution finding.

The solver returns a list of node labels of size 12 which is the unique solution so far (frequency of 1.0).

Solving using the quantum SDK QuTiP

In the previous section, we have used a non-quantum solver to resolve our instance of MIS. In this section, we'll use actually use a quantum algorithm. There are three steps to quantum algorithms:

1. Converting the problem into a Register (the position of atoms in the quantum device) and a set of Pulses (the configuration of lasers on the quantum device)
2. Actually running the Register and Pulse on the quantum device
3. Extracting the results of quantum measurement on the quantum device into a solution to the original problem.

In this library, all three steps are entrusted to backends. This library provides several backends, depending on your use. Since you may not have access to a quantum computer for step 2, we will use the QutipBackend. This is a simple backend that has the advantage of working on most computers, regardless of operating system or GPU.

In [4]:

from mis import BackendConfig, BackendType


solver_config = SolverConfig(
    # Use the QuTIP backend.
    backend = BackendConfig(
        backend = BackendType.QUTIP
    ),
    # Perform up to 10 quantum measures.
    max_iterations=10
)

# Run the solver
solver = MISSolver(instance, config)
solutions = solver.solve()

# Display results
print("MIS solution:", solutions[0].nodes)
print("Solution frequency:", solutions[0].frequency)
print("Solution size:", solutions[0].size)
solutions[0].draw()

preprocessing - current kernel size is 32

MIS solution: [1, 2, 4, 8, 9, 15, 16, 18, 25, 26, 30, 32]
Solution frequency: 1.0
Solution size: 12

Note that any quantum algorithm is, by definition, non-deterministic, so there is no guarantee that this will be the same solution as the non-quantum solver.

Solving using Remote QPU backend

This section illustrates the use of a QPU backend hosted on Pasqal's Cloud Platform. Provided that you are granted with credentials to access the platform, they should be passed to instantiate a RemoteQPUBackend.

In [5]:

# Replace with your username, project id and password on the Pasqal Cloud.
USERNAME="username"
PROJECT_ID="123"
PASSWORD=None

if PASSWORD is not None:
    config = SolverConfig(
        backend = BackendConfig(
            backend=BackendType.REMOTE_QPU,
            username=USERNAME,
            project_id=PROJECT_ID,
            password=PASSWORD
        ),
        max_iterations=10
    )

    # Run the solver
    solver = MISSolver(instance, config)
    solutions = solver.solve()

    # Display results
    print("MIS solution:", solutions[0].nodes)
    print("Solution cost:", solutions[0].frequency)
    solutions[0].draw()